1. Field of the Invention
The present invention relates generally to interpolation methods for automatic generation of an accurate digital elevation model, and more particularly relates to intelligent interpolation methods for accurate extraction of 3-dimentional digital elevation models from satellite images, aerial photographs, or ground surveying.
2. Description of the Related Art
Digital elevation model (DEM) is the topographic data composed of the set of horizontal coordinates (x, y) and its elevation (z) for each grid cell in a given region. The process of DEM can be summarized in three steps; (1) image-matching step to find overlapped regions from stereo images, (2) camera-modeling step to obtain (x,y,z) from the results of the image-match with a camera model relating the photo plane with the absolute ground coordinates, and (3) interpolation step to change the uneven horizontal distribution resulted from camera-model into the uniform horizontal square distribution. In ground surveying, image-match and camera-model could be omitted.
Interpolation is essential for an automatically generated DEM. For a manually generated DEM, interpolation is necessary, but the effect of interpolation is insignificant. Many studies on interpolation have progressed since 1970""s, and focused on finding the optimal interpolation method from dozens of mathematical model such as Gaussian, Kriging, Nearest Neighbor, Moving Window Average, Multiquadric, Modified Shepard, Spline, and Minimum Curvature. We call these old methods as conventional interpolation methods (CIMs).
Since the CIMs handle less than a few hundreds of input data as an experimental trial, following problems show up when the CIMs are applied to the results of the real data; artificial lands are created with the size of the interpolation radius near coast, breakwater, lake, and river. An intellectual interpolation method is introduced to deal with the real data (Krupnik, A., 1998, Automatic detection of erroneous areas in automatic surface reconstruction, Proceedings of ISPRS Commission III Symposium, Columbus, Ohio, p. 132-137). In this method, the edges of a lake or farmland are matched, and the interpolation is performed on the matching results. However, this method can not be applied to the areas with open boundaries such as the sea off the coast and a river.
It is an object of the present invention to provide intelligent interpolation methods for automatic generation of an accurate digital elevation model, which can solve the above-mentioned problems near a coast or a river.
The present invention is composed of three basic processes: The first process (102) of Center-of-Gravity(COG)/Empty-Center-Index(ECI) elimination, which eliminates the artificial elevation off the edge of the stereo-matched region, generated by the result (101) of the conventional interpolation methods if the corresponding COG or ECI is greater than a threshold. The second process (104) of hole-fill segmentation, which segments the eliminated region after the first process (102), and decides whether the eliminated elevation should be reconstructed based upon the size of the segment. And the third process (103) of noise-remove segmentation, which segments the interpolated region after the first process (102), and decides whether the interpolated elevation should be eliminated based upon the size of the segment.
The invention produces an accurate digital elevation model even for the areas with open boundaries off the coast and over a river.